﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0058_SearchMatrix : IAlgorithm
    {
        // 74. 搜索二维矩阵

        // 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
        //  每行中的整数从左到右按升序排列。
        //  每行的第一个整数大于前一行的最后一个整数。

        // 提示：
        //  m == matrix.length
        //  n == matrix[i].length
        //  1 <= m, n <= 100
        //  -10^4 <= matrix[i][j], target <= 10^4

        public void Test()
        {
            // 算法参数定义
            var matrix = new int[][]
            {
                new int[] { 1,4 },
                new int[] { 2,5 }
            };
            var target = 2;
            // 算法执行与打印
            Console.WriteLine(SearchMatrix1(matrix, target));
        }

        // 算法
        // 先二分找所在行，再在所在行二分找值
        public bool SearchMatrix(int[][] matrix, int target)
        {
            int rowIndex = binarySearchFirstColumn(matrix, target);
            if (rowIndex < 0)
            {
                return false;
            }
            return binarySearchRow(matrix[rowIndex], target);
        }
        public int binarySearchFirstColumn(int[][] matrix, int target)
        {
            int low = -1, high = matrix.Length - 1;
            while (low < high)
            {
                int mid = (high - low + 1) / 2 + low;
                if (matrix[mid][0] <= target)
                {
                    low = mid;
                }
                else
                {
                    high = mid - 1;
                }
            }
            return low;
        }
        public bool binarySearchRow(int[] row, int target)
        {
            int low = 0, high = row.Length - 1;
            while (low <= high)
            {
                int mid = (high - low) / 2 + low;
                if (row[mid] == target)
                {
                    return true;
                }
                else if (row[mid] > target)
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }
            return false;
        }

        // 当做一个数组，一次二分法，但若一维数组数量不一致，则无效
        public bool SearchMatrix1(int[][] matrix, int target)
        {
            int m = matrix.Length, n = matrix[0].Length;
            int low = 0, high = m * n - 1;
            while (low <= high)
            {
                int mid = (high - low) / 2 + low;
                int x = matrix[mid / n][mid % n];
                if (x < target)
                    low = mid + 1;
                else if (x > target)
                    high = mid - 1;
                else
                    return true;
            }
            return false;
        }
    }
}
